Problema 1 
Beduini (Clara Ionescu)

	doua oaze A si B se gasesc in desert la distanta de n zile de mers una
de cealalta. O caravana formata din k beduini si un emir trebuie sa traverseze
desertul de la oaza A la oaza B. In desert emirul si beduinii beau zilnic cate 
un litru de apa fiecare. Fiecare beduin poate sa transporte cel mult x litri de
apa. Emirul nu transporta apa.
In oaza A exiata apa in cantitate suficient de mare.
Deplasarea caravanei se v face pe baza urmatoarelor reguli:
- pe traseu se pot crea depozite de apa; fiecare depozit trebuie pazit de un
singur beduin (cat timp in depzit se gaseste apa);
- membrii caravanei se deplaseaza intr-un singu grup impreuna cu emirul, exceptand
pe cei care satu de paza;
- toti membrii caravanei initiale trebuie sa ajunga impreuna (in aceeasi zi) in
oaza B;
- apa poate fi transportata doar din oaza a; din oaza B nu sa va lua apa (chiar
daca astfel s-ar minimiza numarul de zile);
- in oaza B fiecare beduin trebuie sa ajunga cu 0 litri de apa;
	Pentru a asigura in depozitul Di cantitatea de apa necesara avansarii, 
membrii caravanei se pot intoarce in depozitul Di-1 (sau oaza A dupa caz),
rspectand regulile de deplasare enuntate mai sus;
- miscarile caravanei pot avea loc conform urmatoarei scheme:
A<->D1
    D1<->D2
   .............
		Di<->Di+1
		..................
			 Dn<->B
	Sa se planifice modul in care se va traversa desertul pentru a ajunge
din A in B intr-un numar minim de zile.
Intrare:
	Fisierul de intare INPUT.TXT contine 3 numere separate printr-un spatiu
reprezentand numarul de beduini (k), distanta in zile n (1<=n<=50), dintre cele
doua oaze si cantitatea maxima de apa (x) care poate fi transportata de un beduin 
la un moment dat. Aceste date vor avea de asemenea valori intregi, incat rezultatele
se vor putea reprezenta pe 4 octeti.
Iesire:
	Rezultatul se scrie in fisierul OUTPUT.TXt care va avea urmatoarea structura:
- pe prima linie se scrie un numar intreg reprezentand numarul minim de zile in
care se va travera desertul;
- pe a doua linie se scrie cantitatea totala de apa care se va lua din oaza A;
- pe a treia linie se scrie nmarul depozitelor nr create in desert;
	Daca nr<>0 atunci:
- pe urmatoarea linie se scrie distanta de la oaza A la primul depozit si
cantitatea de apa exsitenta in acesta in ziua in care se incepe dplasarea spre
urmatorul depozit; cele doua numere se despart printr-un spatiu.
- pe urmatoarele nr-1 linii se scrie ditanta de la depozitul anterior pana la
cel curent si camtitatea de apa existenta in acesta in ziua in care se incepe 
deplasarea spre urmatorul depozit; (cele doua numere se despart printr-un spatiu);
corespunzator ultimului depozit, aceasta cantitate reprezinta apa necesara 
traversarii drumului pana la oaza B.
- pe ultima linie se scrie distanta intre ultimul depozit si oaza B.
	Daca nr=0, atunci in fisierul de iesire vor apare doar primele trei linii
avand continutul precizat mai sus.
In cazul in care nu se poate traversa desertul, in fisierul de iesire se va scrie
"Imposibil".

Timp necesar pentru un test: 5 secunde.
=================================
Algoritm:

  Problema contine trei cazuri speciale :
Cazul 1. Se pleaca din A pana la primul depozit. La primul drum se utilizeaza
         toti beduinii iar la urmatoarele drumuri se tine cont de beduinul
         lasat de paza.
Cazul 2. Se pleaca dintr-un depozit de pe parcurs (nu din A) fara un beduin
         (cel lasat in acest depozit) si se creeaza urmatorul depozit.
         La urmatoarele drumuri dus-intors se tine cont de cel de-al doilea
         beduin lasat in ultimul depozit. La ultimul drum dus-intors se tine
         cont si de beduinul lasat in depozitul anterior care paraseste
         depozitul ( si care poate cara apa ! ).
Cazul 3. Se pleaca din ultimul depozit si se ajunge in B cu 0l de apa.
  In program am construit o procedura Distanta_Intre care primeste ca date de
intrare distanta pana la un depozit (a),distanta pana la urmatorul depozit (b)
si cantitatea de apa necesara in depozitul b (apa_b) si,pe baza primelor 2
cazuri , calculeaza numarul minim de zile in care se poate aduce acesta
cantitate de apa in b precum si cantitatea minima necesara in depozitul din a.
  Fiecare element B[i,j] al matricei B va contine numarul minim de zile si
cantitatea minima de apa necesara intr-un depozit din i pentru ca sa ajungem
in B cu 0l de apa construind exact j depozite pe drum (inclusiv primul).
  Prima linie a matricei se construieste pe baza datelor initiale (Cazul 3).
  Pentru fiecare din urmatoarele linii se tine cont doar de linia superioara
(calculata anterior) astfel :
       B[j,l].zile =    min   ( <l,k>.zile + B[j-1,k].zile )            [1]
                     l<k<=n-1
unde :
 - B[j-1,k].zile reprezinta numarul minim de zile pentru a ajunge din k
   in B cu 0l apa prin exact j-1 depozite (calculat anterior)
 - <l,k>.zile reprezinta numarul minim de zile pentru a ajunge din depozitul
   situat in l in depozitul din k cu cantitatea de apa necesara (B[j+1,k].apa)
   si in program se reprezinta prin apelul procedurii Distanta_Intre.
   Pentru l=0 se considera "depozitul din A".
  Pentru fiecare element B[j,l] se va tine minte si cantitatea de apa necesara
in depozitul din l pentru a ajunge in B cu 0l apa precum si care este
urmatorul depozit ( valoarea lui k pentru care se indeplineste conditia [1] ).
  Pentru a gasi drumul optim dintre toate elementele de pe prima coloana se
ia acel element cu numarul de zile minim (daca exista). Drumul (format din
succesiunea depozitelor in sens invers) se gaseste plecand de la acest element
si urcand cate o linie pentru fiecare depozit nou gasit pe baza informatiilor
tinute in matricea B.

------------------------------------
program Seicul_si_Beduinii; (Clara Ionescu)
type Tip_Dep=record
       apa:longint;                                           { Apa necesara }
       zile:longint;                                 { Numar de zile necesar }
       up:byte;                               { Legatura la linia superioara }
      end;
var i,j,l,lu,n,m,x:longint;
    zl,ap,min,k:longint;
    b:array[0..50,0..50] of Tip_Dep;                   { Matricea solutiilor }
    fi,fo:text;

procedure Distanta_Intre(a,b:integer;apa_b:longint;var apa_a,zile:longint);
  var m:longint;
      apa_b_:longint;
 begin { Procedura calculeaza apa necesara in depozitul a si numarul de      }
       { zile pentru a putea ajunge in b cu cantitatea de apa_b apa necesara }
  m:=b-a;                                          { Distanta intre depozite }
  if a=0 then         { Cazul I : Se lasa un singur beduin la primul depozit }
   begin
    if (k*x-m*(k+1)-2*m-k*m>=0) and ((k-1)*x>=m*k) and   { Conditii necesare }
       (x*(k-1)-2*m*(k+1)>0) and (apa_b<MaxLongInt) then
{ (k*x-m*(k+1)-2*m-k*m>=0) Apa pe care o pot lua le ajunge pentru dus        }
{                          si intors lasand un beduin de paza ?              }
{ ((k-1)*x>=m*k) Dupa primul drum, apa pe care o pot lua din a sau b le      }
{                ajunge pentru a strabate drumul dus sau intors ?            }
{ (x*(k-1)-2*m*(k+1)>0) Castigul de apa dupa ce au lasat beduinul de paza    }
{                       pentru fiecare drum dus-intors trebuie sa fie pozitiv}
     begin
      apa_a:=k*x;                               { Apa luata din a la inceput }
      zile:=m;                                 { Zile necesare pentru un dus }
      apa_b_:=k*x-m*(k+1);                      { Apa ajunsa in b la inceput }
      while apa_b_<apa_b do   { Cat timp nu s-a complectat apa necesara in b }
       begin
        zile:=zile+2*m;                         { Mai fac un drum dus-intors }
        apa_a:=apa_a+(k-1)*x;                            { Mai iau din a apa }
        apa_b_:=apa_b_+(k-1)*x-2*m*(k+1);              { Mai ajunge in b apa }
       end;
      apa_a:=apa_a-apa_b_+apa_b;   { Scad din apa luata din a acea cantitate }
                                          { luata in surplus la ultimul drum }
     end else begin                           { Daca nu se poate ajunge in b }
      zile:=MaxLongInt;
      apa_a:=MaxLongInt;
     end;
   end else begin                 { Cazul II : Se lasa 2 beduini la depozite }
    k:=k-1;             { Se scade un beduin ( cel lasat in primul depozit ) }
    if (k*x-m*(k+1)-2*m-k*m>=0) and ((k-1)*x>=m*k) and   { Conditii necesare }
       (x*(k-1)-2*m*(k+1)>0) and (apa_b<MaxLongInt) then
     begin
      apa_a:=k*x;                               { Apa luata din a la inceput }
      zile:=m;                                 { Zile necesare pentru un dus }
      apa_b_:=k*x-m*(k+1);                 { Apa ajunsa in b dupa primul dus }
      while apa_b_+x<apa_b do { Cat timp nu s-a complectat apa necesara in b }
       begin { (tin cont ca la ultimul drum mai pot lua iau inca un beduin)  }
        zile:=zile+2*m;                         { Mai fac un drum dus intors }
        apa_a:=apa_a+(k-1)*x;                            { Mai iau din a apa }
        apa_b_:=apa_b_+(k-1)*x-2*m*(k+1);              { Mai ajunge in b apa }
       end;
      apa_a:=apa_a+x;          { Mai iau din a apa cu beduinul lasat de paza }
                                  { care paraseste depozitul la ultimul drum }
      apa_b_:=apa_b_+x;{ Mai ajunge in b apa luata cu beduinul lasat de paza }
      apa_a:=apa_a-apa_b_+apa_b;   { Scad din apa luata din a acea cantitate }
                                          { luata in surplus la ultimul drum }
     end else begin                           { Daca nu se poate ajunge in b }
      zile:=MaxLongInt;
      apa_a:=MaxLongInt;
     end;
    k:=k+1;                      { Se aduna beduinul lasat in primul depozit }
    if apa_a<MaxLongInt then apa_a:=apa_a+zile; { Se aduna si apa pe care o  }
                         { consuma beduinul lasat de paza in depozitul din a }
   end;
 end;

begin
 assign(fi,'INPUT.TXT');
 reset(fi);
 assign(fo,'OUTPUT.TXT');
 rewrite(fo);
 read(fi,k,n,x);                     { Citesc datele din fisierul de intrare }
 for i:=0 to n-1 do
  begin                                   { Calculez prima linie din matrice }
   b[1,i].apa:=(n-i)*(k+1);                { Apa necesara pentru drumul i->n }
   b[1,i].zile:=n-i;            { Numarul de zile necesar pentru drumul i->n }
   if k*x<(n-i)*(k+1) then                 { Daca nu poate parcurge distanta }
    begin
     b[1,i].apa:=MaxLongInt;
     b[1,i].zile:=MaxLongInt;
    end;
   b[1,i].up:=0;                   { Legatura pe linia superioara ( aici 0 ) }
  end;
 for j:=2 to n-1 do                   { Pentru fiecare din urmatoarele linii }
  begin
   for i:=0 to n-j do               { Pentru fiecare depozit presupus in i-> }
    begin
     min:=MaxLongInt;
     for l:=i+1 to n-j+1 do      { Pentru fiecare drum calculat la linia j-1 }
      begin                                                    { din matrice }
       Distanta_Intre(i,l,b[j-1,l].apa,ap,zl);
{ Presupun un depozit in i si celalalt in l si calculez apa si numarul de    }
{ zile necesare beduinilor pentru a ajunge in l cu cata apa le trebuie       }
       if (zl<MaxLongInt) and (b[j-1,l].zile<MaxLongInt) and
          (zl+b[j-1,l].zile<min) then
        begin            { Daca numarul de zile este mai mic decat cel gasit }
         min:=zl+b[j-1,l].zile;                 { atunci acesta este minimul }
         b[j,i].up:=l;  { Salvez pointerul spre depozitul l linia superioara }
         b[j,i].zile:=min;        { Salvez numar de zile pentru drum i->l->B }
         b[j,i].apa:=ap;    { Salvez apa necesara in i pentru drumul i->l->B }
        end;
      end;
     if min=MaxLongInt then                    { Daca nu exista nici un drum }
      begin
       b[j,i].zile:=MaxLongInt;
       b[j,i].apa:=MaxLongInt;
      end;
    end;
  end;
 min:=MaxLongInt;
 for j:=1 to n-1 do if b[j,0].zile<min then { Calculez minimul dintre        }
  begin { elementele de pe prima coloana adica drum de lungime j de la A la B}
   min:=b[j,0].zile;
   zl:=min;
   ap:=b[j,0].apa;
   i:=j;
  end;
 if min=MaxLongInt then                        { Daca nu exista nici un drum }
  begin
   writeln(fo,'Imposibil');                    { Scrie mesajul corespunzator }
  end else begin
   writeln(fo,zl);                                   { Numar de zile necesar }
   writeln(fo,ap);                              { Cantitatea de apa necesara }
   writeln(fo,i-1);                           { Numar de depozite pe parcurs }
   lu:=0;
   l:=0;
   l:=b[i,0].up;
   for j:=i-1 downto 1 do
    begin
     writeln(fo,l-lu,' ',b[j,l].apa);   { Distanta pana la urmatorul depozit }
                   { si cantitatea de apa cu care se ajunge in acel depozit  }
     lu:=l;
     l:=b[j,l].up;                { Legatura la linia superioara din matrice }
    end;
   if i-1>0 then writeln(fo,n-lu);     { Distanta de la ultimul depozit la B }
  end;
 close(fi);
 close(fo);
end.
====================================
Solutia 2 (Vlad Marius):
program Seicul_si_Beduinii;
type tip=record
       apa:longint;
       zile:longint;
       up:byte;
      end;
var i,j,l,lu,n,m,x:longint;
    zl,ap,min,k:longint;
    b:array[0..60,0..60] of tip;
    fi,fo:text;

procedure Distanta_Intre(a,b:integer;apa_b:longint;var apa_a,zile:longint);
  var ii,jj,m:longint;
      apa_b_:longint;

  procedure ProcesareDistanta;
    begin
     if (k*x-m*(k+1)-2*m-k*m>=0) and ((k-1)*x>=m*k) and
        (x*(k-1)-2*m*(k+1)>0) and (apa_b<MaxLongInt) then
      begin
       apa_b_:=0;
       apa_a:=k*x;
       zile:=m;
       apa_b_:=k*x-m*(k+1);
       if apa_b_<apa_b then
        begin
         jj:=(k-1)*x-2*m*(k+1);
         ii:=(apa_b-apa_b_+jj-1) div jj;
         zile:=zile+2*ii*m;
         apa_a:=apa_a+ii*(k-1)*x;
         apa_b_:=apa_b_+ii*((k-1)*x-2*m*(k+1));
        end else begin
         apa_a:=MaxLongInt;
         zile:=MaxLongInt;
        end;
       apa_a:=apa_a-apa_b_+apa_b;
      end else begin
       zile:=MaxLongInt;
       apa_a:=MaxLongInt;
      end;
    end;

 begin { Procedura calculeaza apa necesara in depozitul a si numarul de
         zile pentru a putea ajunge in b cu apa_b necesara               }
  m:=b-a;
  if a=0 then                             { Se lasa un beduin la depozit }
   begin
    ProcesareDistanta;
   end else begin                  { Se lasa 2 beduini la depozite }
    k:=k-1;
    ProcesareDistanta;
    k:=k+1;
    if apa_a<MaxLongInt then apa_a:=apa_a+zile;
   end;
 end;

begin
 assign(fi,'INPUT.TXT');
 reset(fi);
 assign(fo,'OUTPUT.TXT');
 rewrite(fo);
 read(fi,k,n,x);
 for i:=0 to n-1 do
  begin
   b[1,i].apa:=(n-i)*(k+1);
   b[1,i].zile:=n-i;
   if k*x<(n-i)*(k+1) then
    begin
     b[1,i].apa:=MaxLongInt;
     b[1,i].zile:=MaxLongInt;
    end;
   b[1,i].up:=0;
  end;
 for j:=2 to n-1 do
  begin
   for i:=0 to n-j do
    begin
     min:=MaxLongInt;
     for l:=i+1 to n-j+1 do
      begin
       Distanta_Intre(i,l,b[j-1,l].apa,ap,zl);
       if (zl<MaxLongInt) and (b[j-1,l].zile<MaxLongInt) and (zl+b[j-1,l].zile<min) then
        begin
         min:=zl+b[j-1,l].zile;
         b[j,i].up:=l;
         b[j,i].zile:=min;
         b[j,i].apa:=ap;
        end;
      end;
     if min=MaxLongInt then
      begin
       b[j,i].zile:=MaxLongInt;
       b[j,i].apa:=MaxLongInt;
      end;
    end;
  end;
 min:=MaxLongInt;
 for j:=1 to n-1 do if b[j,0].zile<min then
  begin
   min:=b[j,0].zile;
   zl:=min;
   ap:=b[j,0].apa;
   i:=j;
  end;
 if min=MaxLongInt then writeln(fo,'Imposibil')
  else begin
   writeln(fo,zl);
   writeln(fo,ap);
   writeln(fo,i-1);
   lu:=0;
   l:=0;
   l:=b[i,0].up;
   for j:=i-1 downto 1 do
    begin
     writeln(fo,l-lu,' ',b[j,l].apa);
     lu:=l;
     l:=b[j,l].up;
    end;
   if i-1>0 then writeln(fo,n-lu);
  end;
 close(fi);
 close(fo);
end.
====================================
		TESTE:
testul 0:
4 8 10
-----------------
testul 1:
20 9 5
--------------------
testul 2:
1 6 5
------------------
testul 3:
3 10 10
-----------------
testul 4:
3 13 10
-------------------
testul 5:
3 30 20
-------------------
testul 6:
100 50 100
------------------
testul 7:
50 50 18
--------------------
testul 8:
100 50 30
---------------------
testul 9:
3 15 5
========================
Raspunsuri la teste:
Testul 0:
8
40
0
----------------------
testul 1:
67
1407
5
1 798
1 441
1 252
1 147
1 84
4
----------------------
testul 2:
Imposibil
--------------------
testul 3:
52
208
2
2 56
1 28
7
----------------------
testul 4:
1417
5668
5
2 1148
1 392
1 140
1 56
1 28
7
-----------------------
testul 5:
5322
21288
13
3 8532
1 5440
1 3468
1 2216
1 1420
1 912
1 588
1 384
1 252
1 168
1 116
1 80
1 60
15
--------------------------
testul 6:
50
5050
0
----------------------
testul 7:
1052
53652
24
1 47481
1 41922
1 36975
1 32640
1 28815
1 25398
1 22389
1 19788
1 17493
1 15402
1 13617
1 12036
1 10659
1 9384
1 8313
1 7344
1 6477
1 5712
1 5049
2 3927
1 3468
3 2397
3 1632
5 867
17
------------------------------
testul 8:
132
13332
4
2 11514
4 8686
6 5656
9 2929
29
-----------------------------
Testul 9:
Imposibil
============================

	Evaluare:

Program de evaluare (Marius Vlad)
uses crt;
type depozit= record
               dist_pred:longint;
               apa_start:longint;
              end;
var f:text;
    zile_t,litri_c,nr_dep:longint;
    bedu,cap,dist:longint;
    d:array[0..7500] of depozit;
    i:word;
    nr_bun_de_zile:longint;
    zile,consum:longint;
    l_et,c_et:longint;
    ss:string;
    apa_s,apa_d:longint;
    puncte:byte;
procedure afara(s:string;p:byte);
begin
 rewrite(f);
 writeln(s);
 writeln('Puncte obtinute: ',p);
 writeln(f,p);
 close(f);
 readln;
 halt;
end;

begin
 { param 1 - Input }
 { param 2 - Iesirea Programului evaluat}
 { param 3 - Rezultatul corect }
 {       4 - rez.txt}
 clrscr;
 assign(f,paramstr(1));
 reset(f);
 read(f,bedu);
 read(f,dist);
 readln(f,cap);
 close(f);
 assign(f,paramstr(2));
 reset(f);
 readln(f,zile_t);
 readln(f,litri_c);
 readln(f,nr_dep);
 d[0].apa_start:=litri_c;
 d[0].dist_pred:=0;
 for i:=1 to nr_dep do
     begin
      read(f,d[i].dist_pred); readln(f,d[i].apa_start);
     end;
 {$I-}
 d[nr_dep+1].dist_pred:=0;

 readln(f,d[nr_dep+1].dist_pred);
 if d[nr_dep+1].dist_pred=0 then
    d[nr_dep+1].dist_pred:=dist;
 d[nr_dep+1].apa_start:=0;
 close(f);
 assign(f,paramstr(3));
 reset(f);
 readln(f,puncte);
 readln(f,Nr_bun_de_zile);
 readln(f,consum);
 close(f);
 { Verificari }
 assign(f,paramstr(4));

 if zile_t*(bedu+1)<>litri_c then afara('Numarul de zile inmultit cu consumul zilnic nu este egal cu consumul total.',0);
 zile:=0;
 for i:=1 to nr_dep+1 do zile:=zile+d[i].dist_pred;
 if zile<>dist then afara('Suma distantelor dintre depozite nu este egala cu distanta dintre oaze.',0);
 for i:=1 to nr_dep+1 do
     if d[i].apa_start>d[i-1].apa_start then
        begin
         str(i+1,ss);
         afara('In cadrul etapei '+ss+' se realizeaza un consum negativ de apa.',0);
        end;
 { Simularea mersului }
 zile:=0;
 consum:=0;
 for i:=0 to nr_dep do
     begin
      l_et:=d[i+1].dist_pred;
      c_et:=d[i].apa_start-d[i+1].apa_start;
      if (c_et mod (bedu+1)) <> 0 then
         begin
          str(i,ss);
          afara('In cadrul etapei '+ss+' consumul de apa nu este multiplu de beduini.',0);
         end;
      if c_et mod l_et <> 0 then
         begin
          str(i,ss);
          afara('In cadrul etapei '+ss+' consumul de apa nu este multiplu de durata a unei parcurgeri.',0);
         end;
      zile:=zile+c_et div (bedu+1);
      consum:=consum+ c_et;
     end;
 if zile<>zile_t then afara('Insumarea duratelor corespunzatoare fiecarei etape difera de durata totala.',0);
 if consum<>litri_c then afara('Insumarea consumurilor din fiecare etapa nu coincide cu consumul total.',0);
 for i:=1 to nr_dep-1 do
     begin
      apa_s:=d[i].apa_start;
      apa_s:=apa_s-2*cap*(bedu-1);
      l_et:=3;
      while apa_s>0 do
            begin
             inc(l_et,2);
             apa_s:=apa_S-cap*(bedu-2);
            end;
      if (l_et> (d[i].apa_start-d[i+1].apa_start) div (bedu+1) ) then
         begin
          str(i+1,ss);
          afara('In cadrul etapei '+ss+' beduinii cara mai mult decit pot.',0);
         end;

     end;
 if zile_t>nr_bun_de_zile then afara('Numarul de zile este prea mare, dar strategie corecta.',puncte div 2);
 if litri_c>consum then afara('Cantitatea de apa bauta este prea mare.',puncte div 2);
 afara('Rezultat corect!',puncte);
end.
---------------------------------

Baturile pentru evaluare automata:

@ echo off
nume.exe
for %%i in (0 1 2 3 4 5 6 7 8 9) do call runprog %%i
rem chkbedu
--------------------------
@echo Execut programul pentru testul nr. %1
copy  t%1. input.txt
nume.exe
copy  output.txt r%1.
--------------------------
===================================
